/**
 * 堆排序也是一种很高效的算法, 因其吧数组当作二叉树来排序而得名
 *    索引0是树的根节点
 *      除根节点外 任意节点N的父节点是N/2
 *   节点L的左节点是2*L
 *    节点R的右子节点是2*R+1
 */
function heapSort (array) {
  var heapSize = array.length
  buildHeap(array)
  while (heapSize > 1) {
    heapSize--
    swap(array, 0, heapSize) // 交换堆里第一个元素 和最后一个元素的位置 这样 最大的值就会出现在它已排序的位置
    heapify(array, heapSize, 0)
  }
}
function buildHeap (array) {
  var heapSize = array.length
  for (var i = Math.floor(array.length / 2); i >= 0; i--) {
    heapify(array, heapSize, i)
  }
}
function heapify (array, heapSize, i) {
  var left = i * 2 + 1,
    right = i * 2 + 2,
    largest = i
  if (left < heapSize && array[left] > array[largest]) {
    largest = left
  }
  if (right < heapSize && array[right] > array[largest]) {
    largest = right
  }
  if (largest !== i) {
    swap(array, i, largest)
    heapify(array, heapSize, largest)
  }
}